#include "stdafx.h"
#include "ListAlgorithm.h"
#include <iostream>
#include <stack>

void CreateList(Node* head){
	int input;
	while(std::cin>>input){
		AddToTail(head,input);
	}
}

void AddToTail(Node *head,int value){
	Node *node = new Node;
	node->value = value;
	node->next = NULL;
	if(head == NULL )
		return;
	Node *p = head;
	while(p->next != NULL)
		p = p->next;
	p->next = node;
}

void PrintList(Node *head){
	Node *p = head;
	while(p != NULL){
		std::cout<<p->value<<" ";
		p = p->next;
	}
}

void RemoveNode(Node *head, int value){
	if(head == NULL)
		return;
	Node *p = NULL;
	if(head->value == value){
		p = head;
		head = head->next;
		delete p;
	}
	Node *remove = head;
	while(remove->next != NULL && remove->next->value != value)
		remove = remove->next;
	if(remove->next != NULL && remove->next->value == value){
		p = remove->next;
		remove->next = remove->next->next;
		delete p;
	}
}

void PrintListReversingly_Iteratively(Node *head){
	std::stack<Node*> nodes;
	Node *p = head;
	while(p != NULL){
		nodes.push(p);
		p = p->next;
	}
	while(!nodes.empty()){
		Node *p = nodes.top();
		std::cout<<p->value<<" ";
		nodes.pop();
	}
}

void PrintListReversingly_Recursively(Node *head){
	if(head != NULL){
		if(head->next != NULL){
			PrintListReversingly_Recursively(head->next);
		}
		std::cout<<head->value<" ";
	}
}

void DeleteNode(Node *head, Node *toBeDeleted){
	if(head == NULL || toBeDeleted == NULL)
		return;
	Node *p = NULL;
	if(toBeDeleted->next != NULL){
		p = toBeDeleted->next;
		toBeDeleted->value = p->value;
		toBeDeleted->next = p->next;
		delete p;
		p = NULL;
	}else if(head == toBeDeleted){
		delete toBeDeleted;
		toBeDeleted = NULL;
		head = NULL;
	}else{
		 p = head;
		 while(p->next != toBeDeleted)
			 p = p->next;
		 p->next = NULL;
		 delete toBeDeleted;
		 toBeDeleted = NULL;
	}
}

Node* FindKthToTail(Node *head, int k){
	if(head == NULL || k <= 0)
		return NULL;
	Node *front = head, *back = head;
	for(int i = 0; i < k - 1; i++){
		if(front->next == NULL)
			return NULL;
		front = front->next;
	}
	while(front->next != NULL){
		front = front->next;
		back = back->next;
	}
	return back;
}

Node *ReverseList(Node *head){
	if(head == NULL)
		return NULL;
	Node *p = head;
	Node *prev = NULL;
	Node *res = NULL;
	while(p != NULL){
		Node *next = p->next;
		if(next == NULL)
			res = p;
		p->next = prev;
		prev = p;
		p = next;
	}
	return res;
}

Node *MergeList(Node *head1, Node *head2){
	if(head1 == NULL)
		return head2;
	else if(head2 == NULL)
		return head1;
	Node *res = NULL;
	if(head1->value < head2->value){
		res = head1;
		res->next = MergeList(head1->next,head2);
	}else{
		res = head2;
		res->next = MergeList(head1,head2->next);
	}
	return res;
}

Node* FindFirstCommonNode(Node *head1, Node *head2){}